package _18_剑指OfferII;

import java.util.HashMap;
import java.util.Map;

/**
 * 最近使用的放在头结点，不适用的数据靠近最后
 * 因为题目中要求操作都为o(1)，所以可以使用map保存数据，链表达到淘汰策略效果
 */
public class _031_剑指OfferII最近最少使用缓存 {

    private Map<Integer, Node> containers;

    private int capacity;

    // 虚拟头结点， 方便运算
    private Node first;

    // 虚拟尾结点
    private Node last;

    public _031_剑指OfferII最近最少使用缓存(int capacity) {
        this.capacity = capacity;
        this.containers = new HashMap<>();
        first = new Node();
        last = new Node();
        first.next = last;
        last.prev = first;
    }

    public int get(int key) {
        Node node = containers.get(key);
        if (node == null) return -1;
        // 维护顺序
        removeNode(node);
        // 添加至链表头结点
        addFirst(node);
        return node.value;
    }


    public void put(int key, int value) {
        Node node = containers.get(key);
        if (node == null) {
            node = new Node(key, value);
            // 插入
            if (containers.size() == capacity) {
                // 移出最后元素
                removeNode(containers.remove(last.prev.key));
            }
            containers.put(key, node);
        } else {
            // 变更位置
            node.value = value;
            removeNode(node);
        }
        addFirst(node);
    }

    // 从链表中移出元素
    private void removeNode(Node node) {
        // 从链表中移出当前元素
        node.prev.next =  node.next;
        node.next.prev = node.prev;
    }

    private void addFirst(Node node) {
        node.next = first.next;
        first.next.prev = node;
        first.next = node;
        node.prev = first;
    }

    private static class Node {

        int key;

        int value;

        Node next;

        Node prev;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}
